package hot_100;

import java.util.HashMap;

public class 从前序与中序遍历序列构造二叉树 {
    public static void main(String[] args) {

    }

    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        int r = preorder.length - 1;
        return Dfs(preorder, 0, r, 0, r);
    }

    public TreeNode Dfs(int[] preorder, int l0, int r0, int l1, int r1) {
        if (l0 > r0 || l1 > r1)
            return null;
        Integer num = map.get(preorder[l0]);
        TreeNode root = new TreeNode(preorder[l0]);
        root.left = Dfs(preorder, l0 + 1, l0 + num - l1, l1, num);
        root.right = Dfs(preorder, l0+ num - l1 + 1 , r0, num + 1, r1);
        return root;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
